package acwing_03;

import java.util.Scanner;

public class _843_DFS_n皇后问题 {
	// 对角线长度是2n-1，5*5的地图有 9条正对角线 9条反对角线，题目最大值是9，这里开大一点
	static int N = 20;
	static boolean col[] = new boolean[N];// 列 如果有皇后就是true
	static boolean dg[] = new boolean[N];// 正对角线位置 如果有皇后就是true
	static boolean udg[] = new boolean[N];// 反对角线 如果有皇后就是true
	static char path[][] = new char[N][N];// 路径
	
	public static void main(String[] args) {
		Scanner scan = new Scanner(System.in);
		int n = scan.nextInt();
		// 全部初始化为 . 
		for(int i = 0; i < n; i++) {
			for(int j = 0; j < n; j++) {
				path[i][j] = '.';
			}
		}
		// 0表示第0行，第一层搜索
		dfs(0,n);
		scan.close();
		
	}
	public static void dfs(int u,int n) {
		// 这里的u可以看作是行
		// 当 u == n 说明上一次是n-1层，表示第n层已经搜索完毕，则输出结果
		if(u == n) {
			for(int i = 0; i < n; i++) {
				for(int j = 0;j < n; j++) {
					System.out.print(path[i][j]);
				}
				System.out.println();
			}
			System.out.println();
			return;
		}
		// 对列的每个元素进行判断
		for(int i = 0; i < n; i++) {
			// 若该位置没有皇后，则放置皇后并进入下一层的搜索，搜索完恢复现场
			// 每行每列对应 一条正对角线 一条反对角线
			// 正对角线就是：行+列的值  反对角线就是：n - 行 + 列 的值
			if(!col[i] && !dg[u + i] && !udg[n - u + i]) {
				path[u][i] = 'Q';
				col[i] = dg[u + i] = udg[n - u + i] = true;
				dfs(u + 1,n);
				path[u][i] = '.';
				col[i] = dg[u + i] = udg[n - u + i] = false;
			}
		}
	}
}
